"""
图的深度优先搜索（DFS，Depth-First Search）是一种从起点开始，优先沿着一条路径 “走到头”，遇到死胡同再回溯的遍历算法。
DFS 核心逻辑
1：起点选择：从一个未访问的顶点 v 开始（若图有多个连通分量，需遍历所有未访问顶点）。
2：标记访问：将当前顶点 v 标记为 “已访问”（避免重复访问）。
3：递归 / 栈遍历邻接顶点： 对 v 的所有未访问过的邻接顶点，重复步骤 2 和 3（即优先深入一条路径，直到无法继续）。
4：回溯：当一个顶点的所有邻接顶点都已访问，返回到上一个顶点，继续探索其他未访问的邻接顶点。

通俗理解
想象你走迷宫：从入口出发，选一条路一直走到底（遇到岔路先选一条），走到死胡同就回头，回到上一个岔路再选另一条路，直到走遍所有能到达的地方。

关键要点
数据结构：可用 递归（隐式栈） 或 显式栈 实现。
访问标记：必须记录顶点是否已访问（如用集合或数组标记），否则可能陷入死循环（如处理有环图时）。
遍历顺序：不唯一，取决于邻接顶点的遍历顺序（如邻接表中邻点的存储顺序）。

适用场景
路径搜索（如判断两点是否连通）、拓扑排序、连通分量查找、解决迷宫问题等。

题目：实现图的深度优先搜索，从指定顶点开始遍历所有可达顶点。
"""


class Graph:
    def __init__(self, is_directed=False):
        #顶点的字典，key是每一个顶点，value是该顶点的邻接顶点的集合(list类型)
        self.vertices = {}
        self.is_directed = is_directed

    def add_vertex(self, vertex):
        #将一个顶点加入到图中(如果该顶点已经加入，则忽略)
        if vertex not in self.vertices:
            self.vertices[vertex] = []

    def add_edge(self, v1, v2):
        #添加边时，得先向图中加入顶点 有顶点才会有边
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.vertices[v1].append(v2)
        if not self.is_directed:
            #如果是无向图 对应的也要绑定好关系 self.vertices[v2]的值是一个list
            self.vertices[v2].append(v1)

    """支持含有多个连通分量的DFS"""
    def dfs_all(self):
        #所有已经被遍历过的节点的集合
        visited = set()
        #最终按要求遍历得到的集合数据
        result = []
        #该方法是针对一个具体的点开始的迭代
        def dfs_recursive(vertex):
            visited.add(vertex)
            result.append(vertex)
            for neighbor in self.vertices[vertex]:
                if neighbor not in visited:
                    dfs_recursive(neighbor)
        # 遍历所有顶点，对未访问的顶点启动DFS 如此，即可覆盖整个图的所有连通分量
        # 本质就是下面2行代码，来实现对图的其他连通分量的DFS，1：遍历图的所有顶点 2：顶点之前没有访问过  最终确保所有孤立的连通分量都被遍历
        for vertex in self.vertices:
            if vertex not in visited:
                dfs_recursive(vertex)
        return result

    """仅支持从start_vertex所在的连通分量的DFS，对所有连通分量的DFS的支持请看上面dfs_all方法"""
    def dfs(self, start_vertex):
        visited = set()  # 记录已访问的顶点
        result = []  # 存储遍历结果
        def dfs_recursive(vertex):
            visited.add(vertex)
            result.append(vertex)
            # 递归访问所有未访问的邻接顶点
            for neighbor in self.vertices[vertex]:
                if neighbor not in visited:
                    dfs_recursive(neighbor)
        # 检查起始顶点是否存在 很基本的一个简单判断过滤
        if start_vertex not in self.vertices:
            return []
        # 从起始顶点开始DFS
        dfs_recursive(start_vertex)
        return result


graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 5)

graph.add_edge(6, 7)
graph.add_edge(6, 8)
# 图结构:
#     0         6
#    / \       / \
#   1   2     7   8
#  / \   \
# 3   4   5

print("DFS遍历结果:", graph.dfs_all())  # 输出:  [0, 1, 3, 4, 2, 5, 6, 7, 8]
